#include <iostream>
#include <algorithm>
#include <vector>
#include <string>
#include <set>
#include <map>
#include <queue>
using namespace std;
#define int long long

//int s(int s) {
//	return s * s;
//}
//
//signed main() {
//	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	cout << s(2);
//	return 0;
//}

//int n;
//string s;
//
//int find(char a, char b) {
//	for (int i = 0; i < s.size()-1; i++) {
//		if (s[i] == a && s[i + 1] == b)
//			return i;
//		if (s[i] == b && s[i + 1] == a)
//			return i;
//	}
//	return -1;
//}
//
//void solve() {
//	cin >> n >> s;
//	if (n == 1) {
//		cout << "-1\n";
//		return;
//	}
//	int in = 0, tn = 0, ln = 0;
//	for (auto x : s) {
//		if (x == 'I')
//			in++;
//		else if (x == 'T')
//			tn++;
//		else
//			ln++;
//	}
//	int maxn = max({ in,ln,tn });
//	int ndi = maxn-in, ndt = maxn-tn, ndl = maxn-ln;
//	vector <int> ans;
//	bool ok = true;
//	while (ndi || ndl || ndt) {
//		if (ndi) {
//			int index = find('L','T');
//			if (index != -1) {
//				ndi--;
//				s.insert(index + 1, 1, 'I');
//				ans.push_back(index + 1);
//			}
//			else if (ndl == 0 && ndt == 0) {
//				ok = false;
//				break;
//			}
//		}
//		if (ndl) {
//			int index = find('I', 'T');
//			if (index != -1) {
//				ndl--;
//				s.insert(index + 1, 1, 'L');
//				ans.push_back(index + 1);
//			}
//			else if (ndi == 0 && ndt == 0) {
//				ok = false;
//				break;
//			}
//		}
//		if (ndt) {
//			int index = find('I', 'L');
//			if (index != -1) {
//				ndt--;
//				s.insert(index + 1, 1, 'T');
//				ans.push_back(index + 1);
//			}
//			else if (ndl == 0 && ndi == 0) {
//				ok = false;
//				break;
//			}
//		}
//	}
//
//	if (ok) {
//		cout << ans.size() << '\n';
//		for (auto x : ans) {
//			cout << x << '\n';
//		}
//	}
//	else {
//		cout << "-1\n";
//	}
//}
//
//signed main() {
//	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	int t;
//	cin >> t;
//	while (t--) {
//		solve();
//	}
//	return 0;
//}


//struct node {
//    int L, I, T;
//    int tot;
//    vector<pair<int, char>> ops;
//    string s;
//};
//
//bool try_balance(node& now, int aim) {
//    now.ops.clear();
//    now.tot = 3 * aim - (now.L + now.I + now.T);
//    if (now.tot < 0 || now.tot > 2 * now.s.size()) return false;
//
//    int need_L = aim - now.L;
//    int need_I = aim - now.I;
//    int need_T = aim - now.T;
//    if (need_L < 0 || need_I < 0 || need_T < 0) return false;
//
//    string cur = now.s;
//    vector<pair<int, char>> ops;
//    int insertions = 0;
//
//    auto find = [&](char required) -> int {
//        for (int i = 0; i < cur.size() - 1; ++i) {
//            char a = cur[i], b = cur[i + 1];
//            if (a == b) continue;
//            char may;
//            if ((a == 'L' && b == 'I') || (a == 'I' && b == 'L')) may = 'T';
//            else if ((a == 'L' && b == 'T') || (a == 'T' && b == 'L')) may = 'I';
//            else if ((a == 'I' && b == 'T') || (a == 'T' && b == 'I')) may = 'L';
//            if (may == required) return i;
//        }
//        return -1;
//        };
//
//    while (need_L > 0 || need_I > 0 || need_T > 0) {
//        bool ok = false;
//        if (need_L > 0) {
//            int pos = find('L');
//            if (pos != -1) {
//                cur.insert(pos + 1, 1, 'L');
//                ops.emplace_back(pos + 1, 'L');
//                need_L--;
//                ok = true;
//            }
//        }
//        if (!ok && need_I > 0) {
//            int pos = find('I');
//            if (pos != -1) {
//                cur.insert(pos + 1, 1, 'I');
//                ops.emplace_back(pos + 1, 'I');
//                need_I--;
//                ok = true;
//            }
//        }
//        if (!ok && need_T > 0) {
//            int pos = find('T');
//            if (pos != -1) {
//                cur.insert(pos + 1, 1, 'T');
//                ops.emplace_back(pos + 1, 'T');
//                need_T--;
//                ok = true;
//            }
//        }
//        if (!ok) return false;
//        if (ops.size() > 2 * now.s.size()) return false;
//    }
//
//    now.ops = ops;
//    return true;
//}
//
//void solve() {
//    int n;
//    string s;
//    cin >> n >> s;
//
//    node state;
//    state.L = count(s.begin(), s.end(), 'L');
//    state.I = count(s.begin(), s.end(), 'I');
//    state.T = count(s.begin(), s.end(), 'T');
//    state.s = s;
//
//    int maxn= max({ state.L, state.I, state.T });
//    for (int m = maxn; m <= n + 2 * n; ++m) {
//        if (3 * m - n < 0) continue;
//        if (3 * m - n > 2 * n) continue;
//        node tmp = state;
//        if (try_balance(tmp, m)) {
//            cout << tmp.ops.size() << "\n";
//            for (auto& op : tmp.ops) {
//                cout << op.first << "\n";
//            }
//            return;
//        }
//    }
//    cout << "-1\n";
//}
//
//signed main() {
//    ios::sync_with_stdio(false);
//    cin.tie(nullptr);
//    int t;
//    cin >> t;
//    while (t--) solve();
//}

//string s;
//
//int find(char a, char b) {
//	for (int i = 0; i < s.size()-1; i++) {
//		if (s[i] == a && s[i + 1] == b) {
//			return i;
//		}
//		if (s[i] == b && s[i + 1] == a) {
//			return i;
//		}
//	}
//	return -1;
//}
//
//void solve() {
//	int n;
//	cin >> n >> s;
//	if (n == 1) {
//		cout << "-1\n";
//		return;
//	}
//	map<char, int> mp;
//	vector <int> ans;
//	for (int i = 0; i < n; i++) {
//		mp[s[i]]++;
//	}
//	auto it = mp.begin();
//	auto x = it; it++;
//	auto y = it; it++;
//	auto z = it; it++;
//	int need1 = z->second - x->second;
//	int need2 = z->second - y->second;
//	bool ok = true;
//	while (need1 || need2) {
//		if (need1) {
//			int index = find(x->first, z->first);
//			if (index == -1) {
//				if (need2 == 0) {
//					ok = false;
//					break;
//				}
//			}
//			else {
//				ans.push_back(index + 1);
//				s.insert(index,1, x->first);
//				need1--;
//			}
//		}
//		if (need2) {
//			int index = find(y->first, z->first);
//			if (index == -1) {
//				if (need1 == 0) {
//					ok = false;
//					break;
//				}
//			}
//			else {
//				ans.push_back(index + 1);
//				s.insert(index, 1, y->first);
//				need1--;
//			}
//		}
//	}
//	if (ok) {
//		for (int i : ans) {
//			cout << i << '\n';
//		}
//	}
//	else
//		cout << "-1\n";
//
//
//}
//
//signed main() {
//	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
//	int t;
//	cin >> t;
//	while (t--) {
//		solve();
//	}
//	return 0;
//}
//for (int i = 0; i < n - 1; i++) {
//	if (s[i] != s[i + 1]) {
//		if (s[i] != 'I' && s[i + 1] != 'I') {
//			cnt['I']++;
//			index['I'].push(i);
//		}
//		else if (s[i] != 'T' && s[i + 1] != 'T') {
//			cnt['T']++;
//			index['T'].push(i);
//		}
//		else {
//			cnt['L']++;
//			index['L'].push(i);
//		}
//	}
//}
//auto it = mp.begin();
//auto x = it; it++;
//auto y = it; it++;
//auto z = it; it++;
//int need1 = z->second - x->second;
//int need2 = z->second - y->second;
//bool ok = true;
//while (need1 || need2) {
//	if (need1) {
//		if (index[x->first].empty()) {
//			if (need2 == 0) {
//				ok = false;
//				break;
//			}
//		}
//		else
//		{
//			auto i = index[x->first].front(); index[x->first].pop();
//			ans.push_back(i);
//			need1--;
//			index
//
//		}
//	}
//
//}


//int a[200005];
//
//void solve() {
//	int n;
//	cin >> n;
//	bool you = false;
//	bool ji = false;
//	for (int i = 1; i <= n; i++) {
//		cin >> a[i];
//		if (a[i] % 2 == 0)
//			you = true;
//		else
//			ji = true;
//
//	}
//	int ans = 0;
//	int ok = 0;
//	for (int i = 1; i <= n; i++) {
//		ok = max(ok, a[i]);
//		if (a[i] & 1) ans += a[i] - 1;
//		else ans += a[i];
//	}
//	ans++;
//	if (you && ji)
//		cout << ans << '\n';
//	else
//		cout << ok << '\n';
//}

//void solve() {
//	int n;
//	cin >> n;
//	string a, b;
//	cin >> a >> b;
//	int jb = 0, ob = 0;
//	bool ok = true;
//	for (int i = 0; i < n; i++) {
//		char c = b[i];
//		if (c == '0') {
//			if (i & 1)
//				jb++;
//			else
//				ob++;
//		}
//	}
//	for (int i = 0; i < n; i++) {
//		if (a[i] == '1') {
//			if (i & 1) {
//				ob--;
//				if (ob < 0) {
//					ok = false;
//					break;
//				}
//
//			}
//			else {
//				jb--;
//				if (jb < 0) {
//					ok = false;
//					break;
//				}
//			}
//		}
//
//	}
//	if (ok) {
//		cout << "YES\n";
//	}
//	else
//		cout << "NO\n";
//}


//int a[1000];
//set<int> st;
//
//void solve() {
//	int n;
//	cin >> n;
//	for (int i = 1; i <= n; i++) {
//		cin >> a[i];
//	}
//	int ans = 0;
//	sort(a + 1, a + 1 + n);
//	int y = a[n], x = a[1];
//	ans = y - x;
//	cout << ans << '\n';
//}
//int qp(int a, int b) {
//	int res = 1, base = a;
//	while (b) {
//		if (b & 1)res = (res * base) % mod;
//		base = (base * base) % mod;
//		b >>= 1;
//	}
//	return res;
//}

//int n, m;
//cin >> n >> m;
//for (int i = 1; i <= n; i++) {
//	cin >> a[i];
//}
//for (int i = 1; i <= n; i++) {
//	cin >> p[i];
//	a[i] %= m;
//}
//dp[0][0] = 1;
//int sub = 1;
//for (int i = 1; i <= n; i++) {
//	int no = ((qp(p[i], mod - 2) - 1) * p[i]) % mod;
//	sub = (sub * no) % mod;
//	for (int j = 0; j < m; j++) {
//		dp[i][j] = (dp[i - 1][(j - a[i] + m) % m] * p[i]) % mod;
//		dp[i][j] = (dp[i][j] + (dp[i - 1][j] * no) % mod) % mod;
//	}
//}
//
//cout << dp[n][0] << '\n';

//int n, m, k;
//cin >> n >> m >> k;
//int ans = 0;
//for (int i = 1; i <= n; i++) cin >> a[i];
//for (int i = 1; i <= m; i++) cin >> b[i];
//for (int i = 1; i <= k; i++) cin >> c[i];
//
//for (int i = 1; i <= n; i++)
//for (int j = 1; j <= m; j++)
//for (int t = 1; t <= k; t++) {
//	ans = max((a[i] * b[j]) % c[t], ans);
//}
//
//cout << ans << '\n';
//

//set <int> sum;
//set<pair<int, int>> st;
//int ans = 0;
//for (int i = 1; i <= 50; i++) {
//	int a = qp(2, i), b = qp(5, i);
//	int pre = a % 10;
//	while (a >= 10) {
//		a /= 10;
//		pre = a % 10;
//	}
//	a = pre; pre = b % 10;
//	while (b >= 10) {
//		b /= 10;
//		pre = b % 10;
//	}
//	b = pre;
//
//	int x = a * b;
//	if (st.count({ a,b })) {
//
//	}
//	else {
//		st.insert({ a, b });
//	}
//	if (!sum.count(x)) {
//		ans += x;
//		sum.insert(x);
//	}
//}
//cout << ans << '\n';

//int qp(int a, int b) {
//	int res = 1, base = a;
//	while (b) {
//		if (b & 1)res *= base;
//		base *= base;
//		b >>= 1;
//	}
//	return res;
//}

//class date {
//private:
//	int _day;
//	int _month;
//	int _year;
//
//public:
//	date(int year, int month, int day) {
//		_day = day;
//		_month = month;
//		_year = year;
//	}
//
//	static int getmonth(int year, int month) {
//		int day[13] = { 0,31,28,31,30,31,30,31,31,30,31,30,31 };
//		if (month != 2) {
//			return day[month];
//		}
//		else if (year % 400 == 0 || (year % 4 == 0 && year % 100 != 0)) {
//			return 29;
//		}
//		else
//			return 28;
//	}
//
//	int operator-(date b) {
//		int cnt = 0;
//		while (_day != b._day || _month != b._month || _year != b._year) {
//			cnt++;
//			_day++;
//			if (_day > getmonth(_year, _month)) {
//				_day = 1;
//				_month++;
//				if (_month > 12) {
//					_month = 1;
//					_year++;
//				}
//			}
//		}
//		return cnt;
//	}
//};

//void solve() {
//
//	cin >> n >> m;
//	int ret1 = query(1, 1);
//	int ret2 = query(1, m);
//	if (ret1 == 0) {
//		cout << "!" << 1 << ' ' << 1 << '\n';
//		fflush(stdout);
//		return;
//	}
//	if (ret2 == 0) {
//		cout << '!' << 1 << ' ' << m << '\n';
//		fflush(stdout);
//		return;
//	}
//	pair<int, int> r = judge(ret1, ret2);
//	if (r.first > 0) {
//		cout << '!' << r.first << ' ' << r.second << '\n';
//		fflush(stdout);
//		return;
//	}
//
//	if (ret1 < ret2) {
//		int ret4 = query(n, 1);
//		if (ret4 == 0) {
//			cout << '!' << n << ' ' << 1 << '\n';
//		}
//		else {
//			int x = (ret1 - ret4 + n - 1) / 2, y = ret1 - x + 2;
//			cout << '!' << x << ' ' << y << '\n';
//		}
//		fflush(stdout);
//	}
//	else {
//		int ret4 = query(n, m);
//		if (ret4 == 0) {
//			cout << '!' << n << ' ' << m << '\n';
//		}
//		else {
//			int x = (ret2 - ret4 + n + 1) / 2, y = x - 1 + m - ret2;
//			cout << '!' << x << ' ' << y << '\n';
//		}
//		fflush(stdout);
//	}
//}


//int n, m;
//int query(int x, int y) {
//	cout << "?" << x << ' ' << y << '\n';
//	fflush(stdout);
//	int c;
//	cin >> c;
//	return c;
//}
//
//pair<int, int> judge(int d1, int d2) {
//	if ((d1 - d2 + m + 1) % 2 == 1)return { -1,-1 };
//	int y = (d1 - d2 + m + 1) / 2, x = d1 - y - 2;
//	if (y <= 0 || x <= 0)return { -1,-1 };
//
//
//	int ret3 = query(x, y);
//	if (ret3 == 0)return{ x,y };
//	return { 0,0 };
//}